package Lecture9;

import java.util.Arrays;

public class exam {

	private static final Object[] swap = null;


	public static void main(String[] args) 
	{
		
				//[901, 882, 453, 654, 5555, 86, 7, 18, 109, 300]
				//[5555, 901, 453, 654, 882, 86, 7, 18, 109, 300]
				//[7, 18, 86, 109, 300, 453, 654, 882, 901, 5555]


		int[] array = {901,882,453,654,5555,86,7,18,109,300};
		System.out.println(Arrays.toString(array));
		array = buildHeap(array);
		System.out.println(Arrays.toString(array));
		array = sortHeap(array);
		System.out.println(Arrays.toString(array));

	}
	
	
	public static int[] buildHeap (int[] array)
	{
	
		for(int i = 0; i < array.length; i++)
		{
			int node = i;
			
			while(node != 0)
			{
				int parent = (node - 1) / 2;
				
				if(array[parent] < array[node])
				{
					int t = array[parent];
					array[parent] = array[node];
					array[node] = t;
					
				}
				
				node = parent;
			}
			
		}
				
		return array;
	}

	
	public static int[] sortHeap (int[] array)
	{
		buildHeap(array);
		
		
		for(int i = 0; i < array.length; i++)
		{
			int heapLength = array.length-1-i;
			swap(array, 0 , heapLength);
			
			int parent = 0;		
		
		
		
		while(true)
		{
			int left = parent*2 + 1;
			int right = parent*2 + 2;
			
			if(left >= heapLength)      //nqma deca
			{
				break;
			}
			else 
				if (right >= heapLength)   // samo left
				{
					if(array[left] > array[parent])    //left po-golqmo ot perant
					{
						swap(array, left, parent);
						break;
					}
				}
				else									//ima 2 ili poveche deca
					if(array[left] > array[right])      // left po-golqmo ot right
					{
						if (array[left] > array[parent])   //left po-golqmo ot parent
						{
							swap(array, left, parent);
						}
						parent = left;                         
					}
					else
						if(array[right] > array[parent])    // right po-golqmo ot parent
						{
							swap(array, right, parent);
						}
						parent = right;
			
			
		}
		
		
		}
		return array;
	}


	private static void swap(int[] array, int i, int j) 
	{
		int t = array[i];
		array[i] = array[j];
		array[j] = t;

	}
	
	
}
